Asymetric Break Certificates notebook

Breaking RSA Public Key Encryption created with openssl¶

Source notebook: breaking asymetric certs jupyter interactive notebook

A small demonstration how to retrieve private key from public key by integer factorization.

We need to use the OpenSSL unsafe, because for demonstration we do not want seriously big keys.

The factorization is done by sympy, because it is a good science research tool.

Lets start with RSA keys creation with openssl.

%%bash
openssl-unsafe genrsa  -out private_rsa_key.pem 128 2> /dev/null
openssl pkey -pubout -in private_rsa_key.pem -out public_rsa_key.pem 2> /dev/null
openssl rsa -in private_rsa_key.pem -check -noout
cat  public_rsa_key.pem | wc -l

RSA key ok
3

Create some text, and encrypt it with public key.

%%bash
echo "sens" > unencrypted.txt
openssl pkeyutl -encrypt -pubin -inkey public_rsa_key.pem -in unencrypted.txt -out  encrypted.txt 
cat unencrypted.txt
echo
cat encrypted.txt | xxd -p

The history saving thread hit an unexpected error (OperationalError('database is locked')).History will not be written to the database.
sens

9b79d49113b10b0fc6bab059a91bdee4

Decrypt it with private key.

%%bash
openssl pkeyutl -decrypt -inkey private_rsa_key.pem -in encrypted.txt -out  decrypted.txt
cat decrypted.txt

sens

Lets look at the private and public key.

%%bash
openssl pkey -in private_rsa_key.pem -text -noout

Private-Key: (128 bit, 2 primes)
modulus:
    00:bf:5b:da:5c:a1:0e:77:de:41:05:8d:c9:6c:7b:
    91:49
publicExponent: 65537 (0x10001)
privateExponent:
    6c:1d:d5:8e:28:61:28:4f:ac:44:3b:81:a0:de:a2:
    d1
prime1: 16710255007646193503 (0xe7e6c0650cf1975f)
prime2: 15221759033407103063 (0xd33e8d314ad2e057)
exponent1: 11183940604549872371 (0x9b3556b98b433af3)
exponent2: 13752933726675538911 (0xbedc3c5bb5fc13df)
coefficient: 14863620565872574889 (0xce463027610681a9)

%%bash
openssl pkey -pubin -in public_rsa_key.pem -text -noout

Public-Key: (128 bit)
Modulus:
    00:bf:5b:da:5c:a1:0e:77:de:41:05:8d:c9:6c:7b:
    91:49
Exponent: 65537 (0x10001)

%%bash
openssl pkey -pubin -in public_rsa_key.pem -noout -text | awk -F'[ ]' '/Exponent:/{print $2}' | tee pubExp

%%bash
openssl rsa -pubin -in public_rsa_key.pem -modulus | awk -F'=' '{print $2}'  | xargs  -I '{}' echo "ibase=16; {}" | bc | tee modint

254359475113174726019480016394361999689

from sympy.ntheory import factorint
with open('modint', 'rb') as f:
    mod = int(f.read())    
print(mod)

254359475113174726019480016394361999689

primes = factorint(mod)
primes_list = list(primes.keys())
primes_list.sort(reverse=True) # order matters for pinv

[p,q] = primes_list
phi = (p - 1) * (q - 1)
with open('pubExp', 'rb') as f:
    e = int(f.read())
d = pow(e, -1, phi)
dp = d % (p - 1)
dq = d % (q - 1)
pinv = pow(q, -1, p)

p,q, pinv,  dp , dq, d

(16710255007646193503,
 15221759033407103063,
 14863620565872574889,
 11183940604549872371,
 13752933726675538911,
 143711531569809935667896416240266027729)

with open('asn1_rsa', 'wb') as out_file:
    text = (
    "asn1=SEQUENCE:rsa_key\n\n[rsa_key]\n"
    "version=INTEGER:0\n"
    "modulus=INTEGER:"+str(mod)+"\n"
    "pubExp=INTEGER:"+str(e)+"\n"
    "privExp=INTEGER:"+str(d)+"\n"
    "p=INTEGER:"+str(p)+"\n"
    "q=INTEGER:"+str(q)+"\n"
    "e1=INTEGER:"+str(dp)+"\n"
    "e2=INTEGER:"+str(dq)+"\n"
    "coeff=INTEGER:"+str(pinv)+"\n"
    )
    out_file.write(text.encode())

%%bash
openssl asn1parse -genconf asn1_rsa -out recreated.bin
openssl pkey -inform DER -outform PEM -in recreated.bin -out recreated2.pem

    0:d=0  hl=2 l= 100 cons: SEQUENCE          
    2:d=1  hl=2 l=   1 prim: INTEGER           :00
    5:d=1  hl=2 l=  17 prim: INTEGER           :BF5BDA5CA10E77DE41058DC96C7B9149
   24:d=1  hl=2 l=   3 prim: INTEGER           :010001
   29:d=1  hl=2 l=  16 prim: INTEGER           :6C1DD58E2861284FAC443B81A0DEA2D1
   47:d=1  hl=2 l=   9 prim: INTEGER           :E7E6C0650CF1975F
   58:d=1  hl=2 l=   9 prim: INTEGER           :D33E8D314AD2E057
   69:d=1  hl=2 l=   9 prim: INTEGER           :9B3556B98B433AF3
   80:d=1  hl=2 l=   9 prim: INTEGER           :BEDC3C5BB5FC13DF
   91:d=1  hl=2 l=   9 prim: INTEGER           :CE463027610681A9

Parameters are the same.

%%bash
openssl pkey -in private_rsa_key.pem -text -noout > a
openssl pkey -in recreated2.pem -text -noout > b
diff -s a b

Files a and b are identical

The PEM files are different.

%%bash
cat private_rsa_key.pem
echo " "
cat recreated2.pem

But they function the same way.

%%bash
openssl pkeyutl -decrypt -inkey private_rsa_key.pem -in encrypted.txt -out  decrypted.txt
openssl pkeyutl -decrypt -inkey recreated2.pem -in encrypted.txt -out  redecrypted2.txt
cat decrypted.txt
cat redecrypted2.txt

sens
sens

Asymetric Break Certificates notebook

Mathias Green

2024-08-23

Breaking RSA Public Key Encryption created with openssl¶

Done!¶